#include <bits/stdc++.h>
using namespace std;
#define TOSTRING(x) #x
#define CONNECT(x, y) x##y
#define FILEIO(problem, ext, status, stream) freopen(TOSTRING(problem) TOSTRING(ext), #status, stream);
#define ADD 0
#define RMV 1
char s[2001], c;
int buc[128][2];
int dp[2001][2001];
const int INF = 0x3f3f3f3f;
inline int cost(int v, int ind) {
    return (v > 0) ? (buc[v][ind]) : (0);
}
inline int ans(char c) {
    return min(buc[c][0], buc[c][1]);
}
inline int min(int a[], int b[]) {
    return min(min(a[0], a[1]), min(b[0], b[1]));
}
int main() {
    freopen("hw.in", "r", stdin);
    freopen("hw.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    // int len = 0;
    // while(c = getchar()) {
    //     if(isalpha(c)) s[++len] = c;
    //     if(c == '\n' || c == '\r') break;
    // }   //Input 
    ios::sync_with_stdio(false);
    cin >> s + 1;
    int len = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        int av, dv;
        cin >> c >> av >> dv;
        buc[c][ADD] = av;
        buc[c][RMV] = dv;
    }
    if(len == 2) {
        cout << min(buc[s[1]], buc[s[2]]);
        return 0;
    }
    if(len == 3) {
        if(s[1] == s[3]) {
            cout << 0;
            return 0;
        }
    }
    //dp
    for (int i = 2; i <= len; ++i) {  //mid
        for (int j = 1, k = i; k <= len; ++j, ++k) {
            dp[j][k] = INF;
            if(s[j] == s[k]) {
                dp[j][k] = dp[j + 1][k - 1];
            }
            else{
                dp[j][k] = min(dp[j][k], dp[j + 1][k] + ans(s[j])); //动了左边
                dp[j][k] = min(dp[j][k], dp[j][k - 1] + ans(s[k])); //动了右边
            }
        }
    }
    cout << dp[1][len];
    return 0;
}
/*
*/
